package com.jacklei.leetocde305;

import com.jacklei.ch10.DecodeString;

import java.io.Serializable;
import java.util.*;

/*
* 现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。

给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示 受限 节点。

在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目。

注意，节点 0 不 会标记为受限节点。



示例 1：


输入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
输出：4
解释：上图所示正是这棵树。
在不访问受限节点的前提下，只有节点 [0,1,2,3] 可以从节点 0 到达。
示例 2：


输入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
输出：3
解释：上图所示正是这棵树。
在不访问受限节点的前提下，只有节点 [0,5,6] 可以从节点 0 到达。


提示：

2 <= n <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵有效的树
1 <= restricted.length < n
1 <= restricted[i] < n
restricted 中的所有值 互不相同*/
public class reachableNodes {
    public static void main(String[] args) {
        reachableNodes re = new reachableNodes();
        System.out.println(re.reachableNodes(10, new int[][]{{4,1},{1,3},{1,5},{0,5},{3,6},{8,4},{5,7},{6,9},{3,2}}, new int[]{2,7}));
    }//10
//[[4,1],[1,3],[1,5],[0,5],[3,6],[8,4],[5,7],[6,9],[3,2]]
      //  [2,7]
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        int res = 1;

        List<MyNode> myArr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            myArr.add(new MyNode(i));
        }
        HashSet<MyNode> restrict = new HashSet<>();
        for (int i : restricted) {
            restrict.add(myArr.get(i));
        }
        for (int[] edge : edges) {
            MyNode root1 = myArr.get(edge[0]);
            MyNode root2 = myArr.get(edge[1]);
            root1.relax.add(root2);
            root2.relax.add(root1);

        }


                res += finO(myArr.get(0), restrict);

        return res;
    }

    public int finO(MyNode currNode , HashSet<MyNode> restrict){
        int res = 0;
        restrict.add(currNode);
        HashSet<MyNode> relax = currNode.relax;
        for (MyNode next:relax) {
            if(!restrict.contains(next) ){
                res += finO(next,restrict)+1;
            }
        }
        return res;
    }
    class MyNode{
        int value;
        HashSet<MyNode> relax = new HashSet<>();

        public MyNode(int value) {
            this.value = value;
        }
    }
}
